package com.mamingchao.basic.bit.eor;

/**
 * 一个数组的，有两种数出现了奇数次，其他的都出现了偶数次
 * there is a array, two type  elements in it come out as odd times
 * other elements in it come out even times
 *
 * Created by mamingchao on 2020/11/14.
 */
public class FindOddTimesNum1 {
    public static void main(String[] args) {
        int[] arr = new int[] {1,1,2,3,4,5,6,7,7,5,6,4};

        //假设 数组里的a 和b 是 奇数次出现的两个元素
        //eor = a ^ b
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }

        //获取eor 最右侧的1
        //因为a 与b不相同，eor一定不是0，eor一定存在1，我就取最右侧的1
        //000000001000
        int rightOne = eor & (~eor +1);

        int result = 0;

        for (int i = 0; i < arr.length; i++) {
            //取出来 所有在跟rightOne 与==0的，也就是
            //跟rightOne 在二进制写法中 相同位置都是1的 array element，
            //然后他们执行异或
            if ((arr[i] & rightOne) != 0){
                result ^= arr[i];
            }
        }


        System.out.println(result);
        System.out.println(result ^ eor);
    }
}
